#include <stdlib.h>

#include "atom.h"
#include "node.h"
#include "tuple.h"
#include "tree.h"

bool isSpace (char c) {
  unsigned char uc = c;
  return uc == 0 || uc == 9 || uc == 10 || uc == 13 || uc == 32 || uc == 255;
}

std::string trim (const std::string &s) {
  std::string::const_iterator b = s.begin (), e = s.end ();
  while(isSpace (*b) && b < e)
    b++;
  while(isSpace (*(e - 1)) && b < e)
    e--;
  if(b <= e)
    return std::string (b, e);
  else
    return std::string ();
}

bool isInteger (const std::string &s) {
  std::string::const_iterator i = s.begin (), e = s.end ();
  if(i == e)
    return false; // Nil atom is not a number
  if(*i == '-')
    i++; // Skips negation sign
  for(; i != e; i++)
    if(*i < '0' || *i > '9') // No, an atom
      return false;
  return true;
}

inline void identifyQuotes (char c, int &inQuote) {
  switch(c) {
  case '\'':
    if(inQuote != 2)
      inQuote = 1 - inQuote;
    break;
  case '"':
    if(inQuote != 1)
      inQuote = 2 - inQuote;
  }
}

inline void identifyBracketsAndQuotes (char c, int &inBrackets, int &inQuote) {
  switch(c) {
  case '(':
  case '[':
    if(!inQuote)
      inBrackets++;
    break;
  case ')':
  case ']':
    if(!inQuote)
      inBrackets--;
    break;
  default:
    identifyQuotes (c, inQuote);
  }
}

std::string removeGroupComments (const std::string &input,
    const std::string &begin, const std::string &end) {
  std::string s;
  std::string::size_type pos = 0, len = input.length (), beginLen =
      begin.length (), endLen = end.length ();

  while(pos < len && pos != std::string::npos) {
    std::string::size_type endPos = pos;
    int inQuote = 0;

    while(endPos < len) {
      identifyQuotes (input[endPos], inQuote);
      if(input.substr (endPos, beginLen) == begin && !inQuote)
        break;
      endPos++;
    }

    s += input.substr (pos, endPos - pos);
    pos = input.find (end, endPos);
    if(pos != std::string::npos)
      pos += endLen;
  }

  return trim (s);
}

void replaceChar (std::string &s, char c0, char c1) {
  int len = s.length (), pos = 0, inQuote = 0;

  while(pos < len) {
    char c = s[pos];
    if(!inQuote && c == c0)
      s[pos] = c1;
    identifyQuotes (c, inQuote);
    pos++;
  }
}

std::string removeComments (const std::string &input) {

  // Remove Line comments
  std::string s = removeGroupComments (input, "--", "\n");

  // Replace tabs and line breaks with spaces
  replaceChar (s, '\t', ' ');
  replaceChar (s, '\n', ' ');

  // Remove group comments
  return removeGroupComments (s, "-=", "=-");
}

// This is the char* version of the splitter which is faster since the tail is
// not extracted away. The std::string version calls this and is slower
// Separator should be at most 2 characters long
const char *splitChars (const char *buffer, std::string &head,
    const char *separator = " ") {
  while(isSpace (*buffer))
    buffer++;
  int pos = 0, inBrackets = 0, inQuote = 0;

  while(buffer[pos])
    if(inBrackets || inQuote || //
        buffer[pos] != separator[0] || //
        (separator[1] != 0 && buffer[pos + 1] != separator[1]))
      identifyBracketsAndQuotes (buffer[pos++], inBrackets, inQuote);
    else
      break;

  head = std::string (buffer, pos);
  buffer += pos;
  if(*buffer)
    buffer += 1 + (separator[1] != 0);
  return buffer;
}

bool split (std::string &s, std::string &head, std::string &tail,
    const char *separator = " ") {
  const char *t = splitChars (s.c_str (), head, separator);
  if(t) {
    tail = std::string (t);
    return true;
  } else {
    tail.clear ();
    return false;
  }
}

// This time starts the scan from the right
bool rightSplit (std::string &s, std::string &head, std::string &tail,
    const char *separator = " ") {
  const char *buffer = s.c_str ();
  int inBrackets = 0, inQuote = 0;
  unsigned int twoChars = separator[1] != 0;
  std::string::size_type pos = s.length ();
  if(pos <= twoChars)
    return false;
  pos -= twoChars;

  while(pos > 0) { // Note this is an unsigned, meaning it could underflow
    identifyBracketsAndQuotes (buffer[pos--], inBrackets, inQuote);
    if(!inBrackets && !inQuote && buffer[pos] == separator[0] && (!twoChars
        || buffer[pos + 1] == separator[1]))
      goto separatorFound;
  }

  head = s;
  tail.clear ();
  return false;

  separatorFound: head = s.substr (0, pos);
  tail = s.substr (pos + strlen (separator));
  return true;
}

unsigned char hexDigit (char c) {
  if(c >= '0' && c <= '9')
    return c - '0';
  else if(c >= 'a' && c <= 'f')
    return c - 'a' + 10;
  else if(c >= 'A' && c <= 'F')
    return c - 'A' + 10;
  else
    return 0;
}

std::string unquote (std::string s, char quote = '\'') {
  std::string ret;
  ret.reserve (s.size ());

  // We simply assumes the string has quote characters in start and end
  std::string::iterator iter = s.begin () + 1, last = s.end () - 1;
  while(iter < last) {
    char c = *iter++;
    if(c == quote && *iter == quote)
      iter++; // Two quotes substituted by one
    else if(c == '%' && *iter == '%')
      iter++;
    else if(c == '%' && iter + 1 < last) { // %xx represents ASCII code
      c = (hexDigit (*iter) << 4) + hexDigit (*(iter + 1));
      iter += 2;
    }
    ret += c;
  }

  return ret;
}

// Recursive descent operator-based parser
Node *parseNode (const std::string &input) {
  std::string s = trim (input), head, tail;
  if(s.empty () || s == "$")
    return Atom::create ("");
  if(s == "[]")
    return new Tuple;

  // Scans for operator
  int len = s.length ();
  int op = nOperators, leftAssoc = 1, opPos;
  int pos = 0, inBrackets = 0, inQuote = 0;
  for(pos = 0; pos < len; pos++) {
    char ch = s[pos];
    if(isalnum (ch) || ch == '.')
      continue;

    identifyBracketsAndQuotes (ch, inBrackets, inQuote);
    if(inBrackets || inQuote)
      continue;

    for(int i = op - leftAssoc; i >= 0; i--) // Ignore higher precedences
      if(operators[i].name[0] == ch) {
        char op1 = operators[i].name[1]; // More check for double-char operators
        if(op1 != 0 && s[pos + 1] != op1)
          continue;

        op = i;
        leftAssoc = !operators[i].rightAssociation;
        opPos = pos;
      }
  }

  if(op != nOperators) { // Operator found
    const Operator& oper = operators[op];
    std::string head = s.substr (0, opPos);
    const char *tail = s.c_str () + opPos + 1 + (oper.name[1] != 0);

    if(oper.name[0] == ' ') { // A linear list of atoms, or called tuple
      Tuple *p = new Tuple;
      do {
        p->nodes.push_back (trim (head));
      } while(*(tail = splitChars (tail, head)));// Provides O(n) performance
      p->nodes.push_back (trim (head));
      return p;
    } else
      return new Tree (oper.name, (pNode) head, (pNode) tail);
  }

  // Parentheses
  char first = s[0], last = *(s.end () - 1);
  if(first == '(' && last == ')')
    return parseNode (s = s.substr (1, s.length () - 2));

  // Brackets force the node to be a tuple
  if(first == '[' && last == ']') {
    Node *node = parseNode (s = s.substr (1, s.length () - 2));
    if(node->type () == Tuple::ID)
      return node;
    else { // Singleton tuple
      Tuple *tuple = new Tuple;
      tuple->nodes.push_back (node);
      return tuple;
    }
  }

  // A quoted atom?
  if(s.length () > 1) {
    if(first == '\'' && last == '\'')
      return Atom::create (unquote (s));
    else if(first == '"' && last == '"') // A quoted string?
      return new String (unquote (s, '"'));
  }

  // A number?
  if(isInteger (s)) // No, an atom
    return Number::create (atoi (s.c_str ()));
  else
    return Atom::create (s);
}
